# -*- coding: utf-8 -*-
# @File: solution.py
# @Author: Liccsu
# @Time: 8/11/2022 上午12:45
# @Project: AI-01-AStar


from queue import PriorityQueue
from time import monotonic as time

from error import TimeOut, NotFound


class Solution:
    """
    self.begin_node: 初始节点
    self.end_node: 目标节点
    self.current_node: 当前节点
    self.searched_num: 总搜索次数
    self.open: 待搜索表队列
    self.closed: 已搜索表
    self.path_list: 最优解路径
    """

    def __init__(self, begin_node, end_node):
        """
        :param begin_node: 初始状态
        :param end_node: 目标状态
        """
        self.begin_node = begin_node
        self.end_node = end_node
        self.current_node = None
        self.searched_num = 0
        self.open = PriorityQueue()
        self.closed = {}
        self.path_list = []

    def get_best_node(self):
        """
        :return: open 表中估价最小的节点
        """
        return self.open.get()

    def solution_path(self):
        """
        :return: 最终解路径
        """
        temp_node = self.current_node
        self.path_list.append(temp_node)

        while temp_node.parent and temp_node.parent != self.begin_node:
            self.path_list.append(temp_node.parent)
            temp_node = temp_node.parent

        self.path_list.append(self.begin_node)
        return self.path_list.reverse()

    def is_in_closed(self, node):
        """
        :param node: 节点
        :return: 此节点是否已存在于 closed 中
        """
        return str(node.node) in self.closed

    def search(self, search_mode):
        """
        :param search_mode: 搜索算法
        :return: 求解路径
        """
        if search_mode == "astar":
            return self.a_star_search()
        elif search_mode == "bfs":
            return self.bfs_search()
        elif search_mode == "dfs":
            return self.dfs_search()
        else:
            raise ValueError("请选择正确的搜索方式！")

    def a_star_search(self, time_out: int = None):
        """
        :param time_out: 最长搜索时间， 默认无限制
        :return: 求解路径
        """
        end_time = 0
        if time_out is not None:
            if time_out <= 0:
                raise ValueError("'time_out'必须为正整数")
            else:
                end_time = time() + time_out
        # 将起始节点放入 open 中
        self.open.put(self.begin_node)
        self.closed[str(self.begin_node.node)] = self.begin_node

        while not self.open.empty():
            if time_out is not None:
                if end_time - time() <= 0.0:
                    raise TimeOut("搜索超时，或可尝试降低搜索复杂度")
            self.searched_num += 1
            if self.searched_num % 100 == 0:
                print(f"\r已搜索{self.searched_num}次, 当前深度 {self.current_node.d}", end='')

            # 取出 open 中的估价最小的节点置为当前节点 current_node
            # 若 current_node 为目标节点，则成功求解
            self.current_node = self.get_best_node()
            if (self.current_node.node == self.end_node.node).all():
                return self.solution_path()

            # 将所有 current_node 的未被搜索过的子节点放入 open 中
            sub_nodes = self.current_node.sub_nodes()
            for sub_node in sub_nodes:
                if not self.is_in_closed(sub_node):
                    self.open.put(sub_node)
                    self.closed[str(sub_node.node)] = sub_node

    def bfs_search(self, time_out: int = None):
        """
        :param time_out: 最长搜索时间， 默认无限制
        :return: 求解路径
        """
        end_time = 0
        if time_out is not None:
            if time_out <= 0:
                raise ValueError("'time_out'必须为正整数")
            else:
                end_time = time() + time_out
        # 将起始节点放入 open 中
        self.open.queue.append(self.begin_node)
        self.closed[str(self.begin_node.node)] = self.begin_node

        while not self.open.empty():
            if time_out is not None:
                if end_time - time() <= 0.0:
                    raise TimeOut("搜索超时，或可尝试降低搜索复杂度")
            self.searched_num += 1

            # 取出 open 中的第一个节点置为当前节点 current_node
            # 若 current_node 为目标节点，则成功求解
            self.current_node = self.open.queue.pop(0)
            if self.searched_num % 100 == 0:
                print(f"\r已搜索{self.searched_num}次, 当前深度 {self.current_node.d}", end='')
            if (self.current_node.node == self.end_node.node).all():
                return self.solution_path()

            # 将所有 current_node 的未被搜索过的子节点放入 open 中
            sub_nodes = self.current_node.sub_nodes()
            for sub_node in sub_nodes:
                if not self.is_in_closed(sub_node):
                    self.open.queue.append(sub_node)
                    self.closed[str(sub_node.node)] = sub_node

    def dfs_search(self, max_depth: int = None, time_out: int = None):
        """
        :param max_depth: 最大搜索深度，默认无限制
        :param time_out: 最长搜索时间， 默认无限制
        :return: 求解路径
        """
        is_recall = False
        end_time = 0
        self.current_node = self.begin_node
        self.closed[str(self.current_node.node)] = self.current_node
        if max_depth is not None:
            if max_depth <= 0:
                raise ValueError("'max_depth'必须为正整数")
        if time_out is not None:
            if time_out <= 0:
                raise ValueError("'time_out'必须为正整数")
            else:
                end_time = time() + time_out

        while True:
            if time_out is not None:
                if end_time - time() <= 0.0:
                    raise TimeOut("搜索超时，或可尝试降低搜索复杂度")
            self.searched_num += 1
            # 若需要回溯，则将当前节点的父节点置为当前节点
            if is_recall or (max_depth and (self.current_node.d >= max_depth)):
                if is_recall and (self.current_node.node == self.begin_node.node).all():
                    raise NotFound("未搜索到合适的解，或可尝试增大搜索深度")
                self.current_node = self.current_node.parent
            else:
                # 若 current_node 为目标节点，则成功求解
                if (self.current_node.node == self.end_node.node).all():
                    return self.solution_path()

            if self.searched_num % 100 == 0:
                print(f"\r已搜索{self.searched_num}次, 当前深度 {self.current_node.d}", end='')
            is_recall = True
            # 将 current_node 的未被搜索过的一个子节点置为当前节点, 即深度加一
            sub_nodes = self.current_node.sub_nodes()
            for sub_node in sub_nodes:
                # 如果当前节点的所有子节点都已被搜索过，则需要向上回溯一个节点
                if not self.is_in_closed(sub_node):
                    is_recall = False
                    self.current_node = sub_node
                    self.closed[str(sub_node.node)] = sub_node
                    break
